package com.myc.subjects.sort;

import com.myc.subjects.utils.ArrayUtils;

import java.util.Arrays;

/**
 * 快速排序实现
 *
 * 时间复杂度：O(n * log^n)
 *
 * 1. 从数列中挑出一个元素，称为 “基准”（pivot，中心，支点）；
 * 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。这个称为分区（partition）操作。在这个分区退出之后，该基准就处于数列的中间位置（它应该在的位置）；
 * 3. 递归地（recursive）把小于基准值元素的子数列，和大于基准值元素的子数列排序。
 * 这里需要注意，分区操作在具体实现时，可以设置在序列首尾设置双指针，然后分别向中间移动；左指针找到最近的一个大于基准的数，右指针找到最近一个小于基准的数，然后交换这两个数。
 */

public class Kuaisupaixu {

    public static void main(String[] args) {
        int[] nums = new int[]{3, 45, 78, 36, 52, 11, 39, 36, 52};
        Kuaisupaixu k = new Kuaisupaixu();
        k.quicksort(nums, 0, nums.length - 1);
        ArrayUtils.showArray(Arrays.stream(nums).boxed().toArray(Integer[]::new));
    }

    /**
     * 递归方法（分治思想）
     * 递归方法的步骤：
     * 1.定义边界情况（退出递归条件）
     * 2.层层深入前执行语句
     * 3.递归
     * 4.层层浅出后执行语句
     * 5.返回最终形态
     * 这个方法用到了1,2,3
     * 递归方法中只有一个递归调用时，类似一个方法调用的栈，但有多个调用时，形似一个树状的方法调用栈。本题就是一个二叉树。
     */
    public void quicksort(int[] nums, int start, int end){
        //1.定义边界情况
        if(start >= end) return;

        //2.层层深入前执行语句
        //先分区，将数组从基准位置partition切开，得到两个子数组，partition左边的数组元素都比基准元素小，partition右边的数组元素都比基准元素大
        int partition = partition1(nums, start, end);

        //3.递归
        //再对两个子数组递归调用
        quicksort(nums, start, partition - 1);
        quicksort(nums, partition + 1, end);
    }

    //分区方法一：左右指针元素交换
    public int partition1(int[] nums, int start, int end){
        //以第一个元素作为 “基准元素” pivot
        int pivot = nums[start];

        int left = start, right = end;//定义左右指针

        int partition = start;//找到排序后基准元素再数组中的基准位置，并返回

        //使用左右指针从两端开始遍历数组元素，
        while(left < right){
            //从左端找到比基准元素大的元素，从右端找到比基准元素小的元素
            while(left < right && nums[left] <= pivot) left++;
            while(left < right && nums[right] >= pivot) right--;

            //一般情况：交换左右指针对应的两个值
            if(left < right) swap(nums, left, right);
            //特殊情况
            else if(nums[left] < pivot){//右指针遍历到与左指针重合，则左指针位置就是排序后基准元素在数组中的位置
                swap(nums, start, left);//将基准元素交换至排序后基准位置
                partition = left;
            }else{//左指针遍历到与右指针重合，则左指针左边一个位置，就是排序后基准元素在数组中的位置
                swap(nums, start, left - 1);//将基准元素交换至排序后基准位置
                partition = left - 1;
            }
        }
        //此时，基准元素的左边都比基准元素要小，而右边都比基准元素要大
        return partition;//返回基准位置，用于递归调用
    }

    //分区方法二：抢空位
    //将基准元素保存下来，流出start位置的空位，先从右边找到比基准元素小的元素，填充这个空位，又留出了右边的一个空位，再从左边先找到比基准元素大的元素，填充这个空位。依次循环下去，最终左右指针重合留下的位置便是基准位置
    public int partition2(int[] nums, int start, int end){
        int pivot = nums[start];//将基准元素保存下来，流出start位置的空位
        int left = start, right = end;

        while(left < right){
            //先从右边开始找到比基准元素小的元素，填充这个空位，又留出了右边的一个空位
            while(left < right && nums[right] >= pivot) right--;
            nums[left] = nums[right];

            //再从左边先找到比基准元素大的元素，填充这个空位，又留出了左边的一个空位
            while(left < right && nums[left] <= pivot) left++;
            nums[right] = nums[left];
        }
        //最终左右指针重合留下的位置便是基准位置，将pivot填入基准位置
        nums[left] = pivot;
        return left;
    }

    //在nums数组上交换元素的方法
    public void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

/**
 * 总结：
 * 1.快速排序比较重要我之前面试的时候，就有面试官问过我快速排序的实现。面试的时候说或是写快排实现的时候，分区方法写方法二就可以，比较简练工整，但是方法一是其基本思想的直接实现
 * 2.快速排序的实现是一种分治的思想，将一个数组分成两个一大一小的两个子数组，再对子数组进行递归调用
 */
